package p1;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 *2. 两数相加
 给你两个非空 的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

 请你将两个数相加，并以相同形式返回一个表示和的链表。

 你可以假设除了数字 0 之外，这两个数都不会以 0开头。

 来源：力扣（LeetCode）
 链接：https://leetcode.cn/problems/add-two-numbers
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Code02 {
    public static void main(String[] args) {
    }
}

class Solution02 {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode du = new ListNode();
        ListNode cur = du;
        // 进位，每次用完归零
        int carry = 0;

        // 节点不为0,仍然遍历
        while (l1 !=null || l2!=null){
            int sum = 0;
            if (l1!=null){
                // 计算和
                sum+=l1.val;
                // 游标右移
                l1 = l1.next;
            }
            if (l2!=null){
                // 计算和
                sum+=l2.val;
                // 游标右移
                l2 = l2.next;
            }
            sum += carry;
            // 和取模为第一位。
            cur.next=new ListNode(sum%10);
            // 每次都更新carry的值
            carry = sum/10;
            // cur右移
            cur = cur.next;
        }
        // 如果carry>0,说明最高位相加溢出了，直接添加节点，把溢出的1作为值添加进去
        if (carry>0){
            cur.next = new ListNode(carry);
        }
        return du.next;
    }
}

// 定义一个单链表
class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
